def dijkstra(grid, N, start):
    min_dist = [float('inf')] * (N+1)
    visited = [False] * (N+1)
    
    min_dist[start] = 0
    
    
    for i in range(1, N):
        min_data = float('inf')
        cur = -1
        
        for j in range(1, N+1):
            if not visited[j] and min_dist[j] < min_data:
                min_data = min_dist[j]
                cur = j
                
        if cur == -1:
            return min_dist
        
        visited[cur] = True
        
        for j in range(1, N+1):
            if not visited[j] and grid[cur][j] != float('inf') and grid[cur][j]+min_data < min_dist[j]:
                min_dist[j] = grid[cur][j]+min_dist[cur]
    
    return min_dist
    

def main():
    N, M = map(int, input().split())
    grid = [[float("inf")] * (N+1) for _ in range(N+1)]
    
    for i in range(M):
        s, t, value = map(int, input().split())
        grid[s][t] = value
    
    min_dist = dijkstra(grid, N, 1)
    if min_dist[-1] == float('inf'):
        print(-1)
    else:
        print(min_dist[-1])
    return

main()
